package 练习;

import algs4.In;

import java.util.*;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : Test3
 * 功能概要  :
 *
 * @author yangwk
 * @date 2024/6/1 0:00
 */
public class Test3 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String total = in.nextLine();
        Integer n = Integer.parseInt(in.nextLine());
        List<String> operate = new ArrayList<>();
        // 注意 hasNext 和 hasNextLine 的区别
        while (n-- > 0) { // 注意 while 处理多个 case
            operate.add(in.nextLine());
        }
        oper(operate, Integer.parseInt(total));
    }

    public static void oper(List<String> operate, Integer total) {
        Queue<Node> queue = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                int i = -o1.getFreq().compareTo(o2.getFreq());
                return i == 0 ? -o1.getTime().compareTo(o1.getTime()) : i;
            }
        });
        Integer currentTotal = 0;
        HashMap<String, Node> help = new HashMap<>();
        for (String s : operate) {
            String[] s1 = s.split(" ");
            if (s1[0].equals("get")) {
                Node node = help.get(s1[1]);
                node.setTime(System.nanoTime());
                node.setFreq(node.getFreq() + 1);
            } else {
                if (help.containsKey(s1[1])) {
                    Node node = help.get(s1[1]);
                    node.setTime(System.nanoTime());
                } else {
                    if (Integer.parseInt(s1[2]) > total) {
                        queue.clear();
                        break;
                    }
                    while (currentTotal + Integer.parseInt(s1[2]) > total) {
                        Node poll = queue.poll();
                        currentTotal -= poll.getTotal();
                    }
                    currentTotal += Integer.parseInt(s1[2]);
                    Node node = new Node();
                    help.put(s1[1], node);
                    node.setFreq(1);
                    node.setKey(s1[1]);
                    node.setTotal(Integer.parseInt(s1[2]));
                    node.setTime(System.nanoTime());
                    queue.add(node);
                }
            }
        }
        
    }

    public static class Node {
        Long time;
        Integer freq;
        Integer total;
        String key;

        public Long getTime() {
            return time;
        }

        public void setTime(Long time) {
            this.time = time;
        }

        public Integer getFreq() {
            return freq;
        }

        public void setFreq(Integer freq) {
            this.freq = freq;
        }

        public Integer getTotal() {
            return total;
        }

        public String getKey() {
            return key;
        }

        public void setKey(String key) {
            this.key = key;
        }

        public void setTotal(Integer total) {
            this.total = total;
        }
    }


}
